#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <climits>

using namespace std;

// 在排序数组中查找元素的第一个和最后一个位置
class Solution
{
public:
    vector<int> searchRange(vector<int> &nums, int target)
    {
        if (nums.empty())
            return {-1, -1};
        int begin = 0, left = 0, right = nums.size() - 1;
        // 分为2个区间 nums[i] < target nums[i] >= target
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid + 1;
            else
                right = mid;
        }
        if (nums[left] != target)
            return {-1, -1};
        begin = left;
        right = nums.size() - 1;
        // 分为2个区间 target>= nums[i]
        while (left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] <= target)
                left = mid;
            else
                right = mid - 1;
        }
        return {begin, right};
    }
};

class Solution
{
public:
    vector<int> searchRange(vector<int> &nums, int target)
    {
        auto left = std::lower_bound(nums.begin(), nums.end(), target);
        if (left == nums.end() || *left != target)
        {
            return {-1, -1};
        }
        auto right = std::upper_bound(nums.begin(), nums.end(), target) - 1;
        return {static_cast<int>(distance(nums.begin(), left)), static_cast<int>(distance(nums.begin(), right))};
    }
};

// 买卖股票的最佳时机
class Solution
{
public:
    int maxProfit(vector<int> &prices)
    {
        int min_price = INT_MAX;
        int ans = 0;
        for (auto x : prices)
        {
            if (x < min_price)
            {
                min_price = x;
            }
            else if (x - min_price > ans)
            {
                ans = x - min_price;
            }
        }

        return ans;
    }
};

// 两两交换链表中的节点
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution
{
public:
    ListNode *swapPairs(ListNode *head)
    {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode *newhead = new ListNode();
        newhead->next = head;
        // prev 为交换的前一个节点  cur和next是要交换的两个节点,nnext是最后一个节点
        ListNode *prev = newhead, *cur = head, *next = cur->next, *nnext = next->next;
        while (cur && next)
        {
            prev->next = next;
            next->next = cur;
            cur->next = nnext;

            prev = cur;
            cur = nnext;
            if (cur)
                next = cur->next;
            if (next)
                nnext = next->next;
        }

        return newhead->next;
    }
};

// 合并K个升序链表
class Solution
{
public:
    ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        auto cmp = [](ListNode *l1, ListNode *l2)
        { return l1->val > l2->val; };
        priority_queue<ListNode *, vector<ListNode *>, decltype(cmp)> pq(cmp);
        for (auto list : lists)
        {
            if (list)
                pq.push(list);
        }

        ListNode *newhead = new ListNode();
        ListNode *tail = newhead;
        while (pq.size())
        {
            ListNode *cur = pq.top();
            pq.pop();
            ListNode *next = cur->next;
            tail->next = cur;
            tail = cur;
            if (next)
                pq.push(next);
        }

        ListNode *ans = newhead->next;
        delete newhead;
        return ans;
    }
};